0% completed
Problem Statement
You are given two strings s and t. The string t is formed by taking the string s, randomly shuffling all its characters, and then adding one additional character at a random place.
Return the extra character that was added to t.
Examples
-
Example 1:
- Input:
s = "a",t = "aa" - Expected Output:
"a" - Justification: The string
tcontains an extra"a"compared to the strings.
- Input:
-
Example 2:
- Input:
s = "xyz",t = "yxzz" - Expected Output:
"z" - Justification: Besides the characters in
s,thas an additional"z".
- Input:
-
Example 3:
- Input:
s = "lampump",t = "lumpmpap" - Expected Output:
"p" - Justification: After shuffling
sand adding an extra character,tincludes one more"p"thans.
- Input:
Solution
To solve this problem, we will use a character frequency count approach. This method involves counting the frequency of each character in both strings s and t, and then comparing these frequencies to find the character that is extra in t.
This approach is effective because, by identifying the character with a frequency discrepancy, we can pinpoint the additional character in t. This method ensures accuracy regardless of the shuffle, as the order of characters does not impact the frequency count. The simplicity and directness of comparing character frequencies make this approach not only intuitive but also efficient for identifying the added character.
Step-by-Step Algorithm
-
Initialize a Frequency Counter: Start by creating a data structure (like a hash map or dictionary) to keep track of the frequency of each character in the strings
sandt. This will allow us to count how many times each character appears in both strings. -
Count Frequencies in
s: Iterate through each character in the strings. For each character, increase its count in the frequency counter by 1. This step helps us understand the composition ofsin terms of its characters. -
Identify the Extra Character in
t: Now, iterate through each character in the stringt. Decrease its count in the frequency counter by 1 for each occurrence. If at any point, the count for a character goes negative, it indicates that this character is the additional one int(since it appears more times intthan ins). -
Return the Extra Character: The moment you identify a character whose count goes negative, return it. This character is the one that was added to
sto formt.
Algorithm Walkthrough
Let's walk through the algorithm using the given strings s = "lampump" and t = "lumpmpap".
-
Initialize Frequency Map: Start with an empty map.
{} -
Count Characters in
s:- For 'l':
{'l': 1} - For 'a':
{'l': 1, 'a': 1} - For 'm':
{'l': 1, 'a': 1, 'm': 1} - For 'p':
{'l': 1, 'a': 1, 'm': 1, 'p': 1} - For 'u':
{'l': 1, 'a': 1, 'm': 1, 'p': 1, 'u': 1} - For 'm':
{'l': 1, 'a': 1, 'm': 2, 'p': 1, 'u': 1}(incrementing 'm') - For 'p':
{'l': 1, 'a': 1, 'm': 2, 'p': 2, 'u': 1}(incrementing 'p')
- For 'l':
-
Adjust Counts for Characters in
t:- For 'l':
{'l': 0, 'a': 1, 'm': 2, 'p': 2, 'u': 1} - For 'u':
{'l': 0, 'a': 1, 'm': 2, 'p': 2, 'u': 0} - For 'm':
{'l': 0, 'a': 1, 'm': 1, 'p': 2, 'u': 0} - For 'p':
{'l': 0, 'a': 1, 'm': 1, 'p': 1, 'u': 0} - For 'm':
{'l': 0, 'a': 1, 'm': 0, 'p': 1, 'u': 0} - For 'p':
{'l': 0, 'a': 1, 'm': 0, 'p': 0, 'u': 0} - For 'a':
{'l': 0, 'a': 0, 'm': 0, 'p': 0, 'u': 0} - For 'p':
{'l': 0, 'a': 0, 'm': 0, 'p': -1, 'u': 0}(Now, 'p' count is -1, which indicates 'p' is the added character)
- For 'l':
-
Identify the Added Character: Since the frequency of 'p' went to -1, we conclude that 'p' is the character added to
t. Hence, 'p' is returned as the added character.
Code
Complexity Analysis
Time Complexity
The time complexity for all implementations is t). This is because each character in both strings s and t is visited exactly once to increment or decrement their count in the frequency map or object.
Space Complexity
The space complexity is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity